﻿// 2-1 两个字符串的所有最长公共子序列 (20分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
date:20200506-20200507 
user:Dongcheng Li
level:9.5
key:动态规划经典题目
	1.填表的方向是右下
	2.从最后一个往回找考虑相同最长子串的情况，每次递归完要检查是否是最长的子串，不是不能保存。
*/

#include <iostream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
vector<string>shchu;
string daoxu(string C) {
	stack<char>c;
	string C1="";
	for (int i = 0; i < C.size(); i++)
	{
		c.push(C[i]);
	}
	while (!c.empty())
	{
		C1=C1+c.top();
		c.pop();
		
	}
	return C1;
}
int max(int a, int b)
{
	if(a>b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
void digui(string A, string B, string &C,int**mat , int i,int j,int len) {

		do
		{
			if (A[i - 1] == B[j - 1])
			{
				C = C + A[i - 1];
				//cout << A[i - 1] << endl;
				i--;
				j--;
			}
			else if (mat[i][j - 1] > mat[i - 1][j]) {
				j--;

			}
			else if (mat[i][j - 1] < mat[i - 1][j]) {
				i--;

			}
			else
			{
				string D = C;
				digui(A, B, D, mat, i, j-1,len);
				D = C;//point
				digui(A, B, D, mat, i-1, j,len);
				break;
			}

		} while (mat[i][j] != 0);
		//cout << C << endl;
		if (len == C.size()) { 
			shchu.push_back( daoxu(C));
		}
}
int main()
{
	
	stack<int>save_a;
	stack<int>save_b;
	int i, j;
	string C = "";
	string A, B;
	cin >> A >> B;
	int n = A.size();
	int m = B.size();
	//建立矩阵
	int** mat = new int* [n + 1];

	for (i = 0; i < n + 1; i++)
	{
		mat[i] = new int[m + 1];
	}
	//初始化第一行和第一列全为0
	for (i = 0; i < n + 1; i++)
	{
		mat[i][0] = 0;
	}
	for (i = 0; i < m + 1; i++)
	{
		mat[0][i] = 0;
	}
	//建立访问数组并初始化
	int g = max(n, m);
	int* visted = new int[g];
	for (i = 0; i < g; i++)
	{
		visted[i] = 0;
	}
	//由于字符串从零开始读而矩阵从一开始读

	for (i = 1; i < n + 1; i++)
	{
		for (j = 1; j < m + 1; j++)
		{
			if (A[i - 1] == B[j - 1])
			{
				mat[i][j] = mat[i - 1][j - 1] + 1;
				if (visted[mat[i ][j ] ] == 0)
				{

					visted[mat[i][j]] = 1;
					
				}

			}
			else
			{
				mat[i][j] = max(mat[i - 1][j], mat[i][j - 1]);
			}

		}
	
	}
	int len = mat[n][m];
	if (len == 0)
	{
		cout << "NO";
	}
	else//开始回溯
	{
		for (i = 1; i < n + 1; i++)
		{
			for (j = 1; j < m + 1; j++)
			{
				//cout << mat[i][j] << " ";
				if (len == mat[i - 1][j - 1] + 1&& A[i - 1] == B[j - 1])
				{
					save_a.push(i);//A[i - 1] == B[j - 1],记录坐标i，j，他们映射到字符串的i-1和j-1
					save_b.push(j);
				}
		

			}
			//cout <<  "\n";

		}
		//xyxxzxyzxy zxzyyzxxyxxz
		while (!save_a.empty())
		{
			C = "";
			i = save_a.top();

			save_a.pop();
			j = save_b.top();
			//cout << "i " << i << "j " << j << endl;
			save_b.pop();
	
			digui(A, B, C, mat, i, j,len);
			
		}
		
	}
	sort(shchu.begin(),shchu.end());
	for (i = 0; i < shchu.size(); i++)
	{
		cout << shchu[i] ;
		if (i != shchu.size()-1)
		{
			cout << "\n";
		}
	}
}

